package DoExercise.HSP_ZCY.A009_图结构.A001_并查集;

import java.util.HashMap;
import java.util.List;
import java.util.Stack;


/**
 * 有若干个样本a、b、c、d…类型假设是V，在并查集中一开始认为每个样本都在单独的集合里
 * 用户可以在任何时候调用如下两个方法：
 * (1)boolean isSameSet(V x, V y) : 查询样本x和样本y是否属于一个集合
 * (2)void union(V x, V y) : 把x和y各自所在集合的所有样本合并成一个集合
 * 请问怎样才能使得isSameSet和union方法的代价最低？
 */
public class Code01_1并查集
{
    public static class Node<V>
    {
        V value;
        
        public Node(V v)
        {
            value = v;
        }
    }
    
    public static class UnionSet<V>
    {
        public HashMap<V, Node<V>> nodes;//所有节点的表
        public HashMap<Node<V>, Node<V>> parents;//某个节点的父节点
        public HashMap<Node<V>, Integer> sizeMap;//代表点
        
        //初始化
        public UnionSet(List<V> values)
        {
            nodes = new HashMap<>();
            parents = new HashMap<>();
            sizeMap = new HashMap<>();
            for (V value : values)
            {
                Node<V> node = new Node<>(value);
                nodes.put(value, node);
                parents.put(node, node);
                sizeMap.put(node, 1);
            }
        }
        
        /**
         * 填充parents，并扁平化树
         * 减少遍历链的高度
         * <p>
         * 只有第一次扁平化的时候会走全部的复杂度，走完一次扁平化后后面复杂度就是O(1)
         *
         * @param cur
         * @return
         */
        public Node<V> findFather(Node<V> cur)
        {
            Stack<Node<V>> path = new Stack<>();
            while (cur != parents.get(cur))
            {
                path.push(cur);
                cur = parents.get(cur);
            }
            //扁平化
            while (!path.isEmpty())
            {
                parents.put(path.pop(), cur);
            }
            return cur;
        }
        
        //交集
        public boolean isSameSet(V a, V b)
        {
            if (!nodes.containsKey(a) || !nodes.containsKey(b)) return false;
            return findFather(nodes.get(a)) == findFather(nodes.get(b));
        }
        
        //并集
        public void union(V a, V b)
        {
            if (!nodes.containsKey(a) || !nodes.containsKey(b)) return;
            Node<V> aHead = findFather(nodes.get(a));
            Node<V> bHead = findFather(nodes.get(b));
            if (aHead != bHead)
            {
                int aSetSize = sizeMap.get(aHead);
                int bSetSize = sizeMap.get(bHead);
                Node<V> big = aSetSize >= bSetSize ? aHead : bHead;
                Node<V> small = big == aHead ? bHead : aHead;
                parents.put(small, big);//小挂大
                sizeMap.put(big, aSetSize + bSetSize);
                sizeMap.remove(small);
            }
        }
    }
}
